/*
 * @lc app=leetcode.cn id=238 lang=cpp
 *
 * [238] 除自身以外数组的乘积
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 前/后缀和 ~ 数组两侧/矩阵左上右下 连续区域 顺序无关 数值不变
        int n = nums.size();
        std::vector<int> prefix(n, 0);
        std::vector<int> suffix(n, 0);
        int product = 1;
        for (int i=0;i<n;++i){
            product *= nums[i];
            prefix[i] = product;
        }
        product = 1;
        for (int i=n-1;i>=0;--i){
            product *= nums[i];
            suffix[i] = product;
        }

        std::vector<int> res(n, 0);
        res[0] = suffix[1];
        res[n-1] = prefix[n-2];
        for (int i=1;i<n-1;++i){
            res[i] = prefix[i-1] * suffix[i+1];
        }

        return res;
    }
};
// @lc code=end

